Low-Density Parity-Check (LDPC) codes are a type of linear error-correcting codes that are part of the family of linear block codes, which transform a message consisting of a sequence of information symbols of an alphabet into a fixed length sequence of encoding symbols. With linear block codes the input message length is less than the number of encoding symbols thereby providing redundancy allowing for detection and correction of errors. LDPC codes were originally invented by Gallager, see “Low Density Parity-Check Codes” (Monograph, M.I.T. Press, 1963), but little attention was devoted to them at the time, primarily because the required decoding complexity was too high for the processing resources that were available. In 1993, the introduction of turbo codes by Berrou, Glavieux and Thitimajshima, see “Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes” (Proc. IEEE Intl. Comm. Conf., pp 1064-1070, 1993), spurred interest for codes that could achieve error correction at rates approaching the channel capacity of the link they were applied upon. In the intervening 30 years semiconductor devices had gone from expensive Small Scale Integrated Circuits with tens to hundreds of transistors to consumer electronics such as Intel's fifth-generation microarchitecture, the P5 or Pentium, with 3 million transistors. LDPC codes were rediscovered by MacKay in the mid-1990s, see D. J. C. MacKay et al in “Near Shannon Limit Performance of Low Density Parity Check Codes” (Electronics Letters, vol. 32, pp. 1645-1646, August 1996).
LDPC codes are interesting mainly for two reasons. First, they offer an error correction performance that approaches the channel capacity exponentially fast in terms of the code length. Second, the decoding process has linear complexity and a high degree of parallelism that scales with the code length. LDPC codes are capacity approaching codes, meaning that practical constructions exist that allow transmitting information at a signal-to-noise ratio that is very close to the theoretical minimum, known as the Shannon limit. Using iterative belief propagation techniques, LDPC codes can be decoded in time linearly to their block length, a factor particularly beneficial as data rates in communication systems continue to increase.
LDPC codes, therefore, are finding increasing use in applications where reliable and highly efficient information transfer is desired. Although implementation of LDPC codes has lagged that of other codes, notably turbo codes, they are increasingly becoming the standard for error-correction in applications including, but not limited to:                Digital Video Broadcasting-Satellite-Second Generation (DVB-S2) standard;        Forward Error Correction (FEC) within the ITU-T G.hn home network standard providing data rates up to 1 Gb/s over power lines, phone lines and coaxial cables;        IEEE 802.16e WiMAX;        IEEE 802.16n WiFi; and        IEEE 802.3an (10GBase-T Ethernet on CAT6 cables, which operates at 10 Gb/s).        
Of significant importance for such applications, which address high-speed applications in essentially consumer markets, is the ability to implement economically and technically viable decoder circuits, since typically the implementation of the encoder is much less complex. By viable we mean one where the circuits have small die area, and hence low manufacturing cost, efficient power performance, and good processing performance in terms of throughput and latency, yet preserves the error-correction capability of the code.
The design of practical decoding algorithms does not focus so much on the coding gain offered by one code compared to another, but rather on the performance of a given algorithm on a given code. The aim is to optimize error-correction performance versus cost on the widest possible range of codes. Accordingly, throughout the following specification, cost is assessed at the algorithm level, and hence in general terms. Definitive comparisons of the performance/cost ratios of different algorithms can only be made based on actual circuit implementations, but algorithmic efficiencies in component count, speed etc may be implied as offering financial benefit.
At present amongst the challenges related to the decoding of LDPC codes are the decoding complexity of binary error-correction codes themselves and error floors. Decoding complexity for example means that today the codes chosen for IEEE 802.16e WiMAX and IEEE 802.3an Ethernet standards perform roughly 3 dB away from capacity, in part due to the cost of decoding circuits. Accordingly, reducing decoder cost using improved algorithms therefore permits increased efficiency of channel use in such applications.
The phenomenon of error floors refers to the fact that LDPC codes can loose error-correction efficiency when the target error rate is very low. This problem is sometimes studied at the level of the code design, but given that the behavior is influenced by the choice of decoding algorithm and by implementation constraints, it is also possible to address this issue at the algorithm level.
According to embodiments of the invention a new decoding algorithm for LDPC codes is presented that reduces decoding complexity for applications that require high decoding throughput. This algorithm, called the Relaxed Half-Stochastic (RHS) algorithm, uses an approach based on stochastic decoding algorithms, which differs significantly from the conventional approaches of LDPC decoder implementation. Additionally, the RHS algorithm has led, according to other embodiments of the invention, to the invention of a randomized technique called redecoding for addressing the error floor issue. This is the first time, to the inventors knowledge, that such an approach has been taken for reducing error floors, and simulations have shown the error floor can be moved down by several orders of magnitude.
Accordingly, the invention addresses the issues of decoding complexity in high-speed communication systems, thereby allowing reduced cost for implemented decoder circuits, and error floor reduction, thereby allowing improved link performance.